GKR

(updated )

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\set#1{\mathcal #1} \gdef\mat#1{\mathrm #1} \gdef\vec#1{\bm #1} \gdef\popcount{\mathrm{popcount}} \gdef\eq{\mathrm{eq}} \gdef\∀{\mathop{\huge ∀}\limits} \gdef\mul{\mathsf{mul}} \gdef\add{\mathsf{add}} \gdef\addc{\mathsf{add^C}} \gdef\bar#1{\overline{#1}} $$

Last year saw the publication of many interesting new proof systems that deviate from the pattern of doing plonkish-starkish arithmetization on top of a (univariate) polynomial commitment protocol. These new systems are broadly based on two mechanism: folding schemes and sumcheck+GKR. In this note I'll explore sumcheck and GKR.

GKR, introduced in 2008 respectively, is an relatively old protocol. I am not sure why it has thusfar received little attention from implementers, but I suspect it is because the proof sizes are not particularly small and the protocols are arguably more complicated. Proof size was the main metric to benchmark protocols on and here Groth16 is still king, with plonkish-starkish over KZG close behind. Now that it has become practical to recursively verify proofs this is less of a concern, a larger proof can be recursively verified in, say, a Groth16 proof and become small.

The main reason there is renewed interest in GKR protocols is prover complexity. Both Groth16 and plonkish arithmetization require the prover to do $O(n⋅\log n)$ work in the size of the computation. Through clever use of multivariate polynomials the GKR based methods can achieve $O(n)$ prover complexity.

GKR

In GKR08 we have a $k$-layered circuit with the first layer being the input and each further layer computed from the previous one by adding or multiplying two values. For simplicity let's assume each layer has the same number of values $2^n$. We encode each layers values on a $\ps{0,1}^n$ hypercube, creating multi-linear extensions $w_i(\vec x)$ for each layer $i$. The inputs are encoded in $w_0(\vec x)$ and the output will be in $w_k(\vec x)$. The circuit is encoded using two indicator functions, they are MLEs with the following values on the hypercube $\ps{0,1}^{3⋅n}$:

$$ \begin{aligned} \mathrm{add}_i\p{\vec x, \vec y, \vec z} &= \begin{cases} 1 & w_{i+1}(\vec x) = w_i(\vec y) + w_i(\vec z)\\ 0 & \text{otherwise} \end{cases} \\ \mathrm{mul}_i\p{\vec x, \vec y, \vec z} &= \begin{cases} 1 & w_{i+1}(\vec x) = w_i(\vec y) ⋅ w_i(\vec z)\\ 0 & \text{otherwise} \end{cases} \\ \end{aligned} $$

Note that the order of $\vec y$, $\vec z$ is important to avoid double counting, there should be only one $1$ per output node, i.e. for each value of $\vec x$. With these circuit-encoding functions the values on the layers are related by

$$ w_{i+1}(\vec x) = \sum_{\vec y, \vec z ∈ \{0,1\}^n} \p{\hspace{.1em} \begin{aligned} &\phantom{+}\mathrm{add}_i\p{\vec x, \vec y, \vec z} ⋅ \p{w_i(\vec y) + w_i(\vec z)}\\ &+\mathrm{mul}_i\p{\vec x, \vec y, \vec z} ⋅ \p{w_i(\vec y) ⋅ w_i(\vec z)} \end{aligned} \hspace{.5em}} $$

By constuction this holds for $\vec x ∈ \ps{0,1}^n$. To see that it holds for all $\vec x ∈ \F^n$ observe that $\mathrm{add}_i$ and $\mathrm{mul}_i$ are MLEs in $\vec x$ and a linear combination of MLEs is also an MLE. Since MLEs are uniquely identified by their values on $\ps{0,1}^n$ they must be identical. Note that $\mathrm{add}_i$ and $\mathrm{mul}_i$ do not need to be multilinear in $\vec y, \vec z$. In GKR08 a slightly more complex expression is used that does not require multilinearity in $\vec x$ either. The above expression is due to T15.

  1. Prover sends the output values $w_k(\vec x)$.
  2. Verifier sends random $\vec r_{\vec x} ∈ \F^n$ and computes $w_k(\vec r_{\vec x})$.
  3. The prover and verifier run sumcheck on the relation between $w_{k}(\vec r_{\vec x})$ and $w_{k-1}(\vec x)$ as above (using $f$ for the summand) $$ w_k(\vec r_{\vec x}) = \sum_{\vec y, \vec z ∈ \ps{0,1}^n} f(\vec r_{\vec x}, \vec y, \vec z) $$ this results in $\vec c ∈ \F$, random $\vec r_{\vec y}, \vec r_{\vec z} ∈ \F^n$ and a claim $c = f\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$
  4. Prover sends $w_{k-1}(\vec r_{\vec y})$ and $w_{k-1}(\vec r_{\vec z})$, to be proven in a moment.
  5. Verifier computes $\mathrm{add}_{k-1}\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$ and $\mathrm{mul}_{k-1}\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$ locally and checks $c = f\p{\vec r_{\vec x}, \vec r_{\vec y}, \vec r_{\vec z}}$.
  6. The prover and verifier reduce the two queries $w_{k-1}(\vec r_{\vec y})$ and $w_{k-1}(\vec r_{\vec z})$ to one query $w_{k-1}(\vec r_{\vec x}')$.
  7. The prover and verifier run repeat steps 3-6 for $k-1$ more times.
  8. The prover and verifier use further methods to checks $w_0(\vec r_{\vec x})$.

This reduces a claim on the output values $w_k(\vec x)$ to a claim on the input values $w_0(\vec r_{\vec x})$.

Note that it is assumed the verifier knows $\mathrm{add}_i$ and $\mathrm{mul}_i$ and it is economical for the verifier to evaluate it. Alternatively the prover can use a polynomial commitment scheme or other means to convey those values to the verifier.

This protocol can be straightforward generalized to support unequal sized layers $n_i$, leading to potential further reductions in proof size and compute cost.

TODO: Analysis, especially complexity and proof size. Especially efficient evaluation of $\mathrm{add}_i$, $\mathrm{mul}_i$.

Q: The choice of addition and multiplication gates is natural, but also arbitrary. What other gates can be supported? S23 presents a clever scheme using an exponentiation operator.

Quickly evaluating $\add_i$ and $\mul_i$ in random $\vec r$

Observe that in a fully defined circuit each output node has either $\add$ or $\mul$ return $1$ for it. So together they have one-hot on each corner of the $\vec x$ hypercube. We can construct this basis in

$$ \p{2^{n+1} - 4}⋅\mul + n⋅\addc $$

operations.

$$ \mul_i(\vec r_x, \vec r_y, \vec r_z) = \sum_{\vec x ∈ \set M} \eq(\vec x, \vec r_x)⋅ \eq(\vec y(\vec x),\vec r_y)⋅ \eq(\vec z(\vec x),\vec r_z) $$

What remains is computing the various $\eq(\vec c_x, □)$ values. Here $\vec c_x$ encodes the connectivity and is sparse: only $2^n$ out of $2^{2⋅n}$ values are used. We can however again assume that each node is an input at least once. So all values appear. We get $$ 3⋅\p{2^{n+1} - 4}⋅\mul + 3⋅n⋅\addc $$

To compute the three lookup tables for the $\eq$'s. Then to combine them into $\add$ and $\mul$ we need a further $$ 2^{n + 1}⋅\mul $$

  1. Compute the hypercube basis for $\eq(\vec c, \vec r_x)$, $\eq(\vec c, \vec r_y)$ and $\eq(\vec c, \vec r_z)$ in $3⋅2^n$ space.
  2. Use two acumulators $\add$ and $\mul$. For each entry in

See XZZ+19.

References

https://github.com/ingonyama-zk/papers/blob/main/sumcheck_201_chapter_1.pdf

https://eprint.iacr.org/2024/1046

Remco Bloemen
Math & Engineering
https://2π.com